package com.wwy.arithmetic.suanfa.entry;

import lombok.Data;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * 输入：root = [1,null,2,3]
 * 输出：[1,3,2]
 * 示例 2：
 * <p>
 * 输入：root = []
 * 输出：[]
 * 示例 3：
 * <p>
 * 输入：root = [1]
 * 输出：[1]
 */
@Data
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode() {
    }

    public TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

    public static void main(String[] args) {
        TreeNode treeNode1 = new TreeNode();
        treeNode1.val = 1;
        TreeNode treeNode2 = new TreeNode();
        treeNode2.val = 2;
        TreeNode treeNode3 = new TreeNode();
        treeNode3.val = 3;
        TreeNode treeNode4 = new TreeNode();
        treeNode4.val = 4;
        TreeNode treeNode5 = new TreeNode();
        treeNode5.val = 5;
        TreeNode treeNode6 = new TreeNode();
        treeNode6.val = 6;
        treeNode1.left = treeNode2;
        treeNode1.right = treeNode3;
        treeNode2.left = treeNode4;
        treeNode2.right = treeNode5;
        treeNode3.left = treeNode6;
        //     List<Integer> integers = test(treeNode1);
//        for (Integer integer : integers) {
//            System.out.println("integer = " + integer);
//        }

        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(2);
        TreeNode node4 = new TreeNode(3);
        TreeNode node5 = new TreeNode(3);
        TreeNode node6 = new TreeNode(4);
        TreeNode node7 = new TreeNode(4);
        node1.setLeft(node2);
        node1.setRight(node3);
        node2.setLeft(node4);
        node2.setRight(node6);
        node3.setLeft(node5);
        node3.setRight(node7);
        boolean sameTree = isSameTree(node1.getLeft(), node1.getRight());


        int i = maxDepth(node1);
        System.out.println("i = " + i);
        System.out.println("sameTree = " + sameTree);
    }

    public static List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        inorder(root, res);
        return res;
    }

    public static void inorder(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        inorder(root.left, res);
        res.add(root.val);
        inorder(root.right, res);
    }


    /**
     1
     2       3
     4       5 6
     */
    /**
     * 使用队列来解决  先进先出原则
     *
     * @param root
     * @return
     */
    static List<Integer> test(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        Deque<TreeNode> stk = new LinkedList<TreeNode>();
        while (root != null || !stk.isEmpty()) {
            while (root != null) {
                stk.push(root);
                root = root.left;
            }
            root = stk.pop();
            res.add(root.val);
            root = root.right;
        }
        return res;

    }

    /**
     * 查看两个树是否相等
     *
     * @param p
     * @param q
     * @return
     */
    public static boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        } else if (p == null || q == null) {
            return false;
        } else if (p.getVal() != q.getVal()) {
            return false;
        } else {
            return isSameTree(p.getLeft(), q.getLeft()) && isSameTree(q.getRight(), p.getRight());
        }
    }

    /**
     * 二叉树的最大深度
     * 1
     * 2          3
     * 4     5     4    5
     * 6                     7
     */
    public static int maxDepth(TreeNode root) {
        //终止条件：当树为空时结束递归，并返回当前深度0
        if (root == null) {
            return 0;
        }
        //root的左、右子树的最大深度
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);
        //返回的是左右子树的最大深度+1
        return Math.max(leftDepth, rightDepth) + 1;
    }

    /**
     * 二叉树的最小深度
     */
    public static int minDepth(TreeNode root) {
        //终止条件：当树为空时结束递归，并返回当前深度0
        if (root == null) {
            return 0;
        }
        //root的左、右的最小深度
        int leftDepth = minDepth(root.left);
        int rightDepth = minDepth(root.right);
        //返回的是左右子树的最大深度+1
        return Math.min(leftDepth, rightDepth) + 1;
    }
}